<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>O(1)时间复杂度的最小栈设计</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            background: linear-gradient(135deg, #f5f7fa 0%, #c3cfe2 100%);
            min-height: 100vh;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 10px 20px;
            font-size: 14px;
            color: #888;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            color: #d4d4d4;
            line-height: 1.6;
        }
        .keyword { color: #569cd6; }
        .string { color: #ce9178; }
        .comment { color: #6a9955; }
        .function { color: #dcdcaa; }
        .number { color: #b5cea8; }
        .drop-cap {
            float: left;
            font-size: 4rem;
            line-height: 1;
            font-weight: 700;
            margin-right: 0.5rem;
            margin-top: -0.1rem;
            color: #667eea;
            font-family: 'Noto Serif SC', serif;
        }
        .section-number {
            display: inline-flex;
            align-items: center;
            justify-content: center;
            width: 32px;
            height: 32px;
            background: #667eea;
            color: white;
            border-radius: 50%;
            font-weight: 600;
            margin-right: 12px;
            font-size: 16px;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
        .complexity-card {
            background: white;
            border-radius: 12px;
            padding: 20px;
            border-left: 4px solid #667eea;
            transition: all 0.3s ease;
        }
        .complexity-card:hover {
            transform: translateX(5px);
            box-shadow: 0 10px 30px rgba(0,0,0,0.1);
        }
    </style>
</head>
<body>
    <!-- Hero Section -->
    <div class="hero-gradient text-white py-20">
        <div class="container mx-auto px-6 text-center">
            <h1 class="text-5xl font-bold mb-4 tracking-tight">O(1) 时间复杂度的最小栈设计</h1>
            <p class="text-xl opacity-90 max-w-3xl mx-auto">探索如何使用辅助栈策略，在常数时间内实现栈的最小元素查找</p>
            <div class="mt-8 flex justify-center space-x-4">
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full text-sm">
                    <i class="fas fa-layer-group mr-2"></i>数据结构
                </span>
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full text-sm">
                    <i class="fas fa-clock mr-2"></i>时间复杂度 O(1)
                </span>
                <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full text-sm">
                    <i class="fas fa-code mr-2"></i>算法设计
                </span>
            </div>
        </div>
    </div>

    <!-- Main Content -->
    <div class="container mx-auto px-6 py-12 max-w-5xl">
        <!-- Introduction -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-8 card-hover">
            <p class="text-lg leading-relaxed text-gray-700">
                <span class="drop-cap">要</span>在O(1)时间内找到栈中的最小元素，我们需要设计一个数据结构，该结构能够在常数时间内提供栈的最小元素。为了实现这一目标，我们可以采用辅助栈的策略。
            </p>
        </div>

        <!-- Basic Concept -->
        <div class="mb-12">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 flex items-center">
                <i class="fas fa-lightbulb text-yellow-500 mr-4"></i>
                基本思路
            </h2>
            
            <div class="grid md:grid-cols-2 gap-6 mb-8">
                <div class="bg-white rounded-xl shadow-lg p-6 card-hover">
                    <h3 class="text-xl font-semibold mb-4 flex items-center">
                        <span class="section-number">1</span>
                        使用两个栈
                    </h3>
                    <ul class="space-y-3">
                        <li class="flex items-start">
                            <i class="fas fa-database text-blue-500 mt-1 mr-3"></i>
                            <div>
                                <strong class="text-gray-800">主栈（mainStack）</strong>
                                <p class="text-gray-600 mt-1">用于存储实际的栈元素</p>
                            </div>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-chart-line text-green-500 mt-1 mr-3"></i>
                            <div>
                                <strong class="text-gray-800">辅助栈（minStack）</strong>
                                <p class="text-gray-600 mt-1">用于存储当前栈的最小元素，在每次插入元素时维护当前最小值</p>
                            </div>
                        </li>
                    </ul>
                </div>

                <div class="bg-white rounded-xl shadow-lg p-6 card-hover">
                    <h3 class="text-xl font-semibold mb-4 flex items-center">
                        <span class="section-number">2</span>
                        操作的设计
                    </h3>
                    <ul class="space-y-3">
                        <li class="flex items-start">
                            <i class="fas fa-plus-circle text-purple-500 mt-1 mr-3"></i>
                            <div>
                                <strong class="text-gray-800">push操作</strong>
                                <p class="text-gray-600 mt-1">压入主栈，并比较更新辅助栈</p>
                            </div>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-minus-circle text-red-500 mt-1 mr-3"></i>
                            <div>
                                <strong class="text-gray-800">pop操作</strong>
                                <p class="text-gray-600 mt-1">弹出时同步检查辅助栈</p>
                            </div>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-search text-orange-500 mt-1 mr-3"></i>
                            <div>
                                <strong class="text-gray-800">getMin操作</strong>
                                <p class="text-gray-600 mt-1">直接返回辅助栈栈顶元素</p>
                            </div>
                        </li>
                    </ul>
                </div>
            </div>
        </div>

        <!-- Visual Diagram -->
        <div class="bg-white rounded-2xl shadow-xl p-8 mb-12">
            <h3 class="text-2xl font-bold mb-6 text-gray-800 text-center">
                <i class="fas fa-project-diagram text-indigo-500 mr-3"></i>
                数据结构关系图
            </h3>
            <div class="mermaid">
                graph TB
                    A[MinStack 最小栈] --> B[mainStack 主栈]
                    A --> C[minStack 辅助栈]
                    B --> D[存储所有元素]
                    C --> E[存储最小值历史]
                    
                    F[push操作] --> B
                    F --> G{新元素 ≤ 当前最小值?}
                    G -->|是| C
                    
                    H[pop操作] --> I{弹出元素 = 当前最小值?}
                    I -->|是| J[同时弹出辅助栈]
                    
                    K[getMin操作] --> L[返回辅助栈栈顶]
                    
                    style A fill:#667eea,stroke:#fff,stroke-width:3px,color:#fff
                    style F fill:#48bb78,stroke:#fff,stroke-width:2px,color:#fff
                    style H fill:#f56565,stroke:#fff,stroke-width:2px,color:#fff
                    style K fill:#ed8936,stroke:#fff,stroke-width:2px,color:#fff
            </div>
        </div>

        <!-- Implementation Code -->
        <div class="mb-12">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 flex items-center">
                <i class="fas fa-code text-green-500 mr-4"></i>
                实现代码
            </h2>
            
            <p class="text-lg text-gray-700 mb-6">以下是Java的具体实现示例：</p>
            
            <div class="code-block">
                <div class="code-header">
                    <span><i class="fab fa-java mr-2"></i>MinStack.java</span>
                    <button class="text-gray-400 hover:text-white transition-colors">
                        <i class="fas fa-copy"></i>
                    </button>
                </div>
                <pre><code><span class="keyword">import</span> java.util.Stack;

<span class="keyword">class</span> <span class="function">MinStack</span> {
    <span class="keyword">private</span> Stack&lt;Integer&gt; mainStack; <span class="comment">// 主栈</span>
    <span class="keyword">private</span> Stack&lt;Integer&gt; minStack;   <span class="comment">// 辅助栈，用于存储最小值</span>

    <span class="keyword">public</span> <span class="function">MinStack</span>() {
        mainStack = <span class="keyword">new</span> Stack&lt;&gt;();
        minStack = <span class="keyword">new</span> Stack&lt;&gt;();
    }

    <span class="comment">// 将元素推入栈中</span>
    <span class="keyword">public void</span> <span class="function">push</span>(<span class="keyword">int</span> x) {
        mainStack.push(x);
        <span class="comment">// 如果辅助栈为空，或者新元素小于等于当前最小值，则将其压入辅助栈</span>
        <span class="keyword">if</span> (minStack.isEmpty() || x &lt;= minStack.peek()) {
            minStack.push(x);
        }
    }

    <span class="comment">// 移除栈顶元素</span>
    <span class="keyword">public void</span> <span class="function">pop</span>() {
        <span class="keyword">if</span> (!mainStack.isEmpty()) {
            <span class="keyword">int</span> top = mainStack.pop();
            <span class="comment">// 如果弹出的元素是当前最小值，也将其从辅助栈中弹出</span>
            <span class="keyword">if</span> (top == minStack.peek()) {
                minStack.pop();
            }
        }
    }

    <span class="comment">// 获取栈顶元素</span>
    <span class="keyword">public int</span> <span class="function">top</span>() {
        <span class="keyword">if</span> (!mainStack.isEmpty()) {
            <span class="keyword">return</span> mainStack.peek();
        }
        <span class="keyword">throw new</span> IllegalStateException(<span class="string">"Stack is empty"</span>);
    }

    <span class="comment">// 获取最小元素</span>
    <span class="keyword">public int</span> <span class="function">getMin</span>() {
        <span class="keyword">if</span> (!minStack.isEmpty()) {
            <span class="keyword">return</span> minStack.peek();
        }
        <span class="keyword">throw new</span> IllegalStateException(<span class="string">"Stack is empty"</span>);
    }
}</code></pre>
            </div>
        </div>

        <!-- Complexity Analysis -->
        <div class="mb-12">
            <h2 class="text-3xl font-bold mb-8 text-gray-800 flex items-center">
                <i class="fas fa-chart-bar text-purple-500 mr-4"></i>
                操作的复杂度分析
            </h2>
            
            <div class="grid md:grid-cols-2 gap-6">
                <div class="complexity-card">
                    <div class="flex items-center mb-3">
                        <i class="fas fa-plus-